package com.mango.algorithm.sort;

import com.google.common.base.Stopwatch;

import java.util.Arrays;
import java.util.concurrent.TimeUnit;

/**
 * 快速排序
 * 空间复杂度：O(nLogN)
 * 时间复杂度：O(nLogN)
 *
 * 思路：
 * 1. 先选择一个基准点P，以基准点P做分区操作（将比P小的数放到P的左边，等于的放中间，比P大的数放到右边）
 * 2. 然后递归在左边0-小于P的部分排序，sort(0,P)
 * 3. 再递归排右边大于p部分sort(p+1,len)
 * 4. 如果left>=right，则退出
 *
 * 示例：
 * old:[13, 7, 4, 6, 4, 24, 4]
 * num=4 -> [4, 4, 4, 6, 24, 13, 7]
 * num=7 -> [4, 4, 4, 6, 7, 13, 24]
 * result:[4, 4, 4, 6, 7, 13, 24]耗时:9ms
 */
public class QuickFastSort {
    public static void main(String[] args) {
        Stopwatch sw = Stopwatch.createStarted();
        int[] nums = {13,7,4,6,4,24,4};
        System.out.println("old:"+ Arrays.toString(nums));
        System.out.println("result:"+Arrays.toString(sort(nums))+"耗时:"+sw.elapsed(TimeUnit.MILLISECONDS)+"ms");
    }

    public static int[] sort(int[] nums){
        quickSort(nums,0,nums.length-1);
        return nums;
    }
    // 快速排序
    public static void quickSort(int[] nums,int left,int right){
        if(left >= right){
            return ;
        }
        // 基准坐标，分区
        int[] p = partition(nums,left,right);
        // 递归排左边的
        quickSort(nums,left,p[0]-1);
        // 递归排右边的
        quickSort(nums,p[1]+1,right);
    }

    // 对arr[l...r]部分进行partition操作
    // 荷兰国旗问题分区
    private static int[] partition(int[] nums, int left, int right) {
        // 基准值，选中间值，也可以随机选
        int p = (left + right) / 2;
        // 将基准值和right交换
        swap(nums,p,right);
        // lt表示小于区域,i是遍历指针,gt表示大于区域
        int lt = left-1;
        int gt = right;
        int i = left;
        int num = nums[p];
        while (i < gt){
            if(nums[i] < num){
                // 小于当前数的，交换指针位置和小于区域下一个位置，小于区域和指针右移
                swap(nums,++lt,i++);
            }else if(nums[i] == num){
                i++; // 等于num，指针右移
            }else{
                // 大于当前数的，指针和大于区域前一位交换，大于区域左移
                swap(nums,--gt,i);
            }
        }
        // 将基准值放回到gt位置
        swap(nums,gt,right);
        System.out.println("num="+num + " -> " + Arrays.toString(nums));
        return new int[]{lt+1,gt};
    }

    // 交换数组下标
    public static void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
